import java.util.*;

/**
 * 472. 连接词
 * https://leetcode-cn.com/problems/concatenated-words/
 */
public class Solutions_472 {
    Trie_472 root;

    public static void main(String[] args) {
//        String[] words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
        String[] words = {"cat", "catcat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
        // output: {"catcat", "catsdogcats", "dogcatsdog", "ratcatdogcat"}
        // "catsdogcats"由"cats",  "dog" 和 "cats"组成;
        // "dogcatsdog"由"dog",  "cats"和"dog"组成;
        // "ratcatdogcat"由"rat",  "cat",  "dog"和"cat"组成。

        Solutions_472 obj = new Solutions_472();
        List<String> result = obj.findAllConcatenatedWordsInADict(words);
        System.out.println(result);
    }

    /**
     * 解法二：哈希表（32ms）
     */
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> set = new HashSet<>(10000);
        List<String> res = new ArrayList<>();
        int min = Integer.MAX_VALUE;
        for (String word : words) {
            if (word.length() == 0) {
                continue;
            }
            set.add(word);
            // 比较得到 words 中字符串的最小长度，最小为 1
            min = Math.min(min, word.length());
        }
        for (String word : words) {
            // 检查每一个 word
            boolean flag = check(set, word, 0, min);
            if (flag) {
                res.add(word);
            }
        }
        return res;
    }

    public static boolean check(Set<String> set, String word, int start, int min) {
        // 若最小长度为 3，那么能够包含两个及以上的单词的长度最小为 6，循环区间 [3, len - 3]
        for (int i = start + min; i <= word.length() - min; i++) {
            // 字符串的前半部分
            String before = word.substring(start, i);
            if (set.contains(before)) {
                // 字符串的后半部分
                String after = word.substring(i);
                if (set.contains(after)) {
                    // 前半段与后半段的子串都是存在于单词列表中
                    return true;
                }
                boolean flag = check(set, after, 0, min);
                if (flag) {
                    // 仅前半段子串的单词在单词列表中，但是后半段子串的单词却是可以分割的，且分割后的单词，存在于单词列表中
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 解法一：前缀树（82ms）
     */
    public List<String> findAllConcatenatedWordsInADict2(String[] words) {
        root = new Trie_472();
        // 构建树
        insertTrie(words);
        List<String> res = new ArrayList<>();
        for (String word : words) {
            if (word == null || word.length() == 0) {
                // 空串时不需要查找
                continue;
            }
            // 对每个字符串进行查找
            char[] arr = word.toCharArray();
            boolean flag = searchTrie(root, arr, 0, 0);
            if (flag) {
                res.add(word);
            }
        }
        return res;
    }

    /**
     * 通过 dfs 进行查找字符串
     */
    public boolean searchTrie(Trie_472 node, char[] arr, int index, int count) {
        for (int i = index; i < arr.length; i++) {
            int j = arr[i] - 'a';
            if (node.childs[j] == null) {
                return false;
            }
            node = node.childs[j];
            if (node.isEnd) {
                // 若当前节点是一个字符串的结束节点，则可以将之后的字符串再次递归，需要重新从根节点查找
                boolean flag = searchTrie(root, arr, i + 1, count + 1);
                if (flag) {
                    return true;
                }
            }
            // 当 index 后面的子串，分解为单词后，不存在给定的单词列表中时，那么继续向后查找
        }
        // 判断条件，当前节点是结束条件，并且从根节点到node路径上，
        // 组成的字符串中，可以分割为两个及以上的存在于单词列表中的单词
        return node.isEnd && count > 0;
    }

    public void insertTrie(String[] words) {
        for (String word : words) {
            if (word == null || word.length() == 0) {
                // 空串时不需要建树
                continue;
            }
            Trie_472 cur = root;
            char[] arr = word.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                int j = arr[i] - 'a';
                if (cur.childs[j] == null) {
                    cur.childs[j] = new Trie_472();
                }
                cur = cur.childs[j];
            }
            cur.isEnd = true;
        }
    }
}

class Trie_472 {
    Trie_472[] childs;
    boolean isEnd;

    public Trie_472() {
        childs = new Trie_472[26];
    }
}
